#include<iostream>
#include<vector>

using namespace std;

void swap(vector<int>& a, int i, int j){
    int temp = a[j];
    a[j] = a[i];
    a[i] = temp;
    cout << "in swap" << endl;
}

int main(){
    vector<int> a{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    //外循环，左边的为排好序的值
    // for (int i = 0; i < a.size(); i++){
    //     int mi = i;
    //     for (int j = i + 1; j < a.size(); j++){
    //         if(a[j] < a[mi]){
    //             mi = j;
    //         }
    //     }
    //     swap(a, i, mi);
    // }


    //测试递归的写法
    // void recursive_sort(vector<int>& a, int i, int j);
    // recursive_sort(a, 0, a.size());


    //测试改进的选择排序
    void improve_sort(vector<int>& a, int left, int right);
    improve_sort(a, 0, a.size());
    for (int i = 0; i < a.size(); i++){
        cout << a[i] << " ";
    }
    cout << endl;

}

//选择排序也可以写成递归的形式
// void recursive_sort(vector<int>& a, int i, int j){
//     //递归结束条件
//     if(i>=j){
//         return;
//     }
//     int find_min(vector<int>& a, int i, int j);
//     int mi = find_min(a, i, j);
//     swap(a, i, mi);
//     recursive_sort(a, i + 1, j);
// }

// int find_min(vector<int>& a, int i, int j){
//     int mi = i;
//     for (int k = i + 1; k < j; k++){
//         if(a[k] < a[mi]){
//             mi = k;
//         }
//     }
//     return mi;
// }

//选择排序的一种改进，同时找最大最小元素
void improve_sort(vector<int>& a, int left, int right){
    for (int i = 0; i < right/2; i++){
        int min_index = i;
        int max_index = right - i - 1;
        for (int j = min_index; j <= max_index; j++){
            if(a[j] < a[min_index]){
                min_index = j;
            }
            if(a[j] > a[max_index]){
                max_index = j;
            }
        }
        swap(a, min_index, i);
        swap(a, max_index, right - i - 1);
    }
}
